<!DOCTYPE html> 
<html><!-- InstanceBegin template="/Templates/page.dwt" codeOutsideHTMLIsLocked="false" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link rel="stylesheet" href="http://www.hypertextbookshop.com/compilers2013/Stylesheets/prettify.css" />
<link rel="stylesheet" href="http://www.hypertextbookshop.com/compilers2013/Stylesheets/pageStylesheet.css" />
<link rel="stylesheet" href="http://www.hypertextbookshop.com/compilers2013/Stylesheets/navigationStylesheet.css" />
<link rel="stylesheet" href="http://www.hypertextbookshop.com/compilers2013/Stylesheets/allTextStyles.css" />
<link rel="stylesheet" href="http://www.hypertextbookshop.com/compilers2013/Stylesheets/colors-blue.css" />
<script type="text/javascript" src="http://www.hypertextbookshop.com/compilers2013/Scripts/google-code-prettify/run_prettify.js"></script>
<script language="javascript" type="text/javascript" src="http://www.hypertextbookshop.com/compilers2013/Scripts/recomputeAttributes.js"></script>


<!-- InstanceBeginEditable name="doctitle" -->
<title>Design Tradeoffs</title>
<!-- InstanceEndEditable -->
</head>

<body id="body-style">

<!-- 
<div id="browser-window-veil">
</div>
-->

<div id="page-container">

<header id="header">
<div id="track-icon1">
  <img src="http://www.hypertextbookshop.com/compilers2013/Media/StyleImages/bobcat-small.png" width="75" height="48"></div>
<div id="track-icon2">
</div>
<div id="track-icon3">
</div>
  <div id="headMatter">
    <span id="headTitle1">
    Team Portfolios
    </span>
    <span id="headTitle2">
    </span>
  </div>
</header>

<nav id="navigate">
</nav>


<aside id="aside-left">
<div id="asideLeftTitle">
Compilers 2013
</div>

</aside>

<aside id="aside-right">
</aside>

<footer id="footer">
  <div id="footMatter">
    <span id="previousPageLink">

    </span>
    <span id="currentPageNumber">
    </span>
    <span id="nextPageLink">

    </span>
  </div>
</footer>

<article id="mainContent">
<!-- InstanceBeginEditable name="Main" -->
<h1>Design Tradeoffs</h1>
(Describe a design trade-off decision (e.g. execution time vs. space requirements or compile time) in your capstone project and justify the design decisions that you made.)
<ul>
	<li><h2>Scanner Design Tradeoffs</h2></li>
	<ul>
		<li><h3>Resolution of Keywords</h3></li>
		<li> We created a hash table that has all the keywords listed in it. When an identifier is encountered, the hash table is accessed to see if the identifier is a reserved keyword. </li>
		<li> Average time complexity for searching for a word in a hash table is O(1). This indicates that the amount of time required for searching the hash table is constant, irrelevant of its size.</li>
		<li> Instead of hash table, other ADTs like arrays were considered. The average time complexity of arrays is much higher than that of hash tables for searching and sorting.</li>
	</ul>
	<li><h2>Symbol Table Tradeoffs</h2></li>
	<ul>
		<li><h3>Symbol Table Design</h3></li>
		<li> The symbols are stored in the symbol table in a binary tree structure, in non-case sensitive lexicographical order.</li>
		<li> The average time complexity for search and insert actions is O(log n).</li>
		<li> A hash table could be used here, but binary trees are more memory-efficient. They do not reserve more memory than they need.</li>
	</ul>
</ul>
<!--<h3>. . . </h3>-->
<!-- InstanceEndEditable -->

</article>
</div>
</body>
<!-- InstanceEnd --></html>
